|
In computational geometry, a maximum disjoint set (MDS) is a largest set of non-overlapping geometric shapes selected from a given set of candidate shapes. Finding an MDS is important in applications such as automatic label placement, VLSI circuit design, and cellular frequency division multiplexing. Every set of non-overlapping shapes is an independent set in the intersection graph of the shapes. Therefore, the MDS problem is a special case of the maximum independent set (MIS) problem. Both problems are NP complete, but finding a MDS may be easier than finding a MIS in two respects: * For the general MIS problem, the best known exact algorithms are exponential. In some geometric intersection graphs, there are sub-exponential algorithms for finding a MDS.〔, 〕 * The general MIS problem is hard to approximate and doesn't even have a constant-factor approximation. In some geometric intersection graphs, there are polynomial-time approximation schemes (PTAS) for finding a MDS. The MDS problem can be generalized by assigning a different weight to each shape and searching for a disjoint set with a maximum total weight. In the following text, MDS(''C'') denotes the maximum disjoint set in a set ''C''. == Greedy algorithms == Given a set ''C'' of shapes, an approximation to MDS(''C'') can be found by the following greedy algorithm: * INITIALIZATION: Initialize an empty set, ''S''. * SEARCH: For every shape ''x'' in ''C'': *# Calculate ''N(x)'' - the subset of all shapes in ''C'' that intersect ''x'' (including ''x'' itself). *# Calculate the largest independent set in this subset: ''MDS(N(x))''. *# Select an ''x'' such that ''|MDS(N(x))|'' is minimized. * Add ''x'' to ''S''. * Remove ''x'' and ''N(x)'' from ''C''. * If there are shapes in ''C'', go back to Search. * END: return the set ''S''. For every shape ''x'' that we add to ''S'', we lose the shapes in ''N(x)'', because they are intersected by ''x'' and thus cannot be added to ''S'' later on. However, some of these shapes themselves intersect each other, and thus in any case it is not possible that they all be in the optimal solution ''MDS(S)''. The largest subset of shapes that ''can'' all be in the optimal solution is ''MDS(N(x))''. Therefore, selecting an ''x'' that minimizes ''|MDS(N(x))|'' minimizes the loss from adding ''x'' to ''S''. In particular, if we can guarantee that there is an ''x'' for which ''|MDS(N(x))|'' is bounded by a constant (say, ''M''), then this greedy algorithm yields a constant ''M''-factor approximation, as we can guarantee that: Such an upper bound ''M'' exists for several interesting cases: 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Maximum disjoint set」の詳細全文を読む スポンサード リンク
|